/*  supowit.cpp
 * Copyright (C) 2010, Francisco Claude & Patrick Nicholson, all rights reserved.
 *
 * Francisco Claude & Patrick Nicholson <(fclaude|p3nichol)@cs.uwaterloo.ca>
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include "supowit.h"

class VectCmp {
  public:
    bool operator()(vector<Point*>* v1,vector<Point*>* v2) {
      if((*v1)[0]->getY() < (*v2)[0]->getY()) return false;
      return true;
    }
};

size_t find_chain(Point * p, vector<vector<Point*>*> & v) {
  size_t i = 0;
  double actMin = numeric_limits<double>::max();
  size_t index = v.size();
  for(i = 0; i < v.size(); i++)
    if((*v[i])[0]->getY() >= p->getY()) {
      if((*v[i])[0]->getY() < actMin) {
        index = i;
        actMin = (*v[i])[0]->getY();
      }
    }
  return index;
}

vector<vector<Point*>*> supowit(vector<Point*> points) {
  size_t n = points.size();
  vector<vector<Point*>*> ret;
  if(n==0) return ret;
  PointXCmpDes cmp;
  sort(points.begin(),points.end(),cmp);
  vector<Point*>* tmp = new vector<Point*>();
  tmp->push_back(points[0]);
  ret.push_back(tmp);
  size_t chains = 1;
  for(size_t i=1;i<n;i++) {
    size_t pos = find_chain(points[i],ret);
    if(pos == chains) {
      tmp = new vector<Point*>();
      tmp->push_back(points[i]);
      ret.insert(ret.begin(), tmp);
    } else {
      ret[pos]->insert(ret[pos]->begin(), points[i]);
    }
    chains = ret.size();
  }

  vector<vector<Point*>*> realret;
  for(size_t i=0; i<chains; i++) {
    vector<Point*> * newv = new vector<Point*>();
    newv->insert(newv->begin(),ret[i]->rbegin(),ret[i]->rend());
    realret.push_back(newv);
    delete ret[i];
  }

  return realret;
}

